package com.future;

/**
 * Description: 1504. 统计全 1 子矩形
 *
 * @author weiruibai.vendor
 * Date: 2022/11/9 09:38
 */
public class Solution_1504 {

    static Solution_1504 instance = new Solution_1504();

    public static void main(String[] args) {
        int[][] mat = new int[][]{
                {0, 1, 1, 0},
                {0, 1, 1, 1},
                {1, 1, 1, 0},
        };
        mat = new int[][]{
                {1, 0, 1},
                {1, 1, 0},
                {1, 1, 0},
        };
        mat = new int[][]{
                {0, 1, 0, 1},
                {1, 1, 1, 0},
                {0, 1, 0, 1},
        };
        System.out.println(instance.numSubmat(mat));
        System.out.println(instance.numSubmat_dp(mat));
    }

    /**
     * 还未完成
     *
     * @param mat
     * @return
     */
    public int numSubmat_dp(int[][] mat) {
        if (mat == null || mat.length == 0) {
            return 0;
        }
        int N = mat.length;
        int M = mat[0].length;
        int[][] U2D = new int[N][M];
        int[][] L2R = new int[N][M];
        L2R[0][0] = mat[0][0];
        U2D[0][0] = mat[0][0];
        for (int i = 1; i < M; i++) {
            L2R[0][i] = mat[0][i] == 1 ? L2R[0][i - 1] + 1 : 0;
            U2D[0][i] = mat[0][i] == 1 ? 1 : 0;
        }
        for (int i = 1; i < N; i++) {
            U2D[i][0] = mat[i][0] == 1 ? U2D[i - 1][0] + 1 : 0;
            L2R[i][0] = mat[i][0] == 1 ? 1 : 0;
        }
        for (int i = 1; i < N; i++) {
            for (int j = 1; j < M; j++) {
                L2R[i][j] = mat[i][j] == 1 ? L2R[i][j - 1] + 1 : 0;
            }
        }
        for (int j = 1; j < M; j++) {
            for (int i = 1; i < N; i++) {
                U2D[i][j] = mat[i][j] == 1 ? U2D[i - 1][j] + 1 : 0;
            }
        }
        int ans = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                ans += U2D[i][j] + L2R[i][j] - 1;
                if (U2D[i][j] > 1 && L2R[i][j] > 1) {
                    /**
                     * 以(i,j)为左下角，边成从2开始扩展
                     * eg:
                     * 1、边长为2
                     * (i-1,j-1) (i-1,j)
                     * (i,j-1)   (i,j)
                     * ...
                     */
                    int maxWidth = L2R[i][j];
                    int maxHeight = U2D[i][j];
                    int width = 2;
                    int height = 2;
                    int x = i;
                    int y = j;
                    while (width <= maxWidth) {

                    }

                }
            }
        }
        return ans;
    }

    /**
     * 超时
     * 假设mat长度行N,高M
     *
     * @param mat
     * @return
     */
    public int numSubmat(int[][] mat) {
        if (mat == null || mat.length == 0) {
            return 0;
        }
        int N = mat.length;
        int M = mat[0].length;
        int ans = 0;
        for (int height = 1; height <= N; height++) { // 高 不是下标，所以<=
            for (int width = 1; width <= M; width++) { // 宽 不是下标 所以<=
                for (int i = 0; i < N; i++) {
                    for (int j = 0; j < M; j++) {
                        // 固定一点，向左延伸width，向下延伸height,看是否形成矩形
                        if (verifyIsRectangle(mat, i, j, i + height, j + width)) {
                            ans++;
                        }
                    }
                }
            }
        }

        return ans;
    }

    private boolean verifyIsRectangle(int[][] mat, int x1, int y1, int x2, int y2) {
        int N = mat.length;
        int M = mat[0].length;
        if (x2 > N || y2 > M) {
            return false;
        }
        for (int i = x1; i < x2; i++) {
            for (int j = y1; j < y2; j++) {
                if (mat[i][j] != 1) {
                    return false;
                }
            }
        }
        //System.out.println("(" + x1 + "," + y1 + ")(" + (x2 - 1) + "," + (y2 - 1) + ")");
        return true;
    }


}
